<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>合并两个有序链表 - 算法可视化</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Hiragino Sans GB", Simsun, sans-serif;
            background-color: #f8fafc;
            color: #1e293b;
        }
        .hero {
            background: linear-gradient(135deg, #4f46e5 0%, #7c3aed 100%);
        }
        .code-block {
            background-color: #1e293b;
            color: #e2e8f0;
            border-radius: 0.5rem;
            overflow: hidden;
        }
        .code-header {
            background-color: #334155;
            padding: 0.75rem 1rem;
            color: #94a3b8;
            font-family: 'Noto Sans SC', monospace;
        }
        .code-body {
            padding: 1rem;
            font-family: 'Noto Sans SC', monospace;
        }
        .card {
            transition: transform 0.3s ease, box-shadow 0.3s ease;
        }
        .card:hover {
            transform: translateY(-4px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .highlight {
            position: relative;
        }
        .highlight::after {
            content: '';
            position: absolute;
            left: 0;
            bottom: 0.1em;
            width: 100%;
            height: 0.4em;
            background-color: rgba(79, 70, 229, 0.3);
            z-index: -1;
            transition: height 0.3s ease;
        }
        .highlight:hover::after {
            height: 0.6em;
        }
    </style>
</head>
<body class="min-h-screen">
    <!-- Hero Section -->
    <section class="hero text-white py-20 px-4 sm:px-6 lg:px-8">
        <div class="max-w-5xl mx-auto">
            <h1 class="text-4xl md:text-5xl lg:text-6xl font-bold mb-6 font-serif">合并两个有序链表</h1>
            <p class="text-xl md:text-2xl text-white/90 max-w-3xl mb-8">将两个升序链表合并为一个新的升序链表<br>掌握归并思想在链表操作中的应用</p>
            <div class="flex flex-wrap gap-4 mt-10">
                <div class="flex items-center bg-white/10 backdrop-blur-sm px-4 py-2 rounded-lg">
                    <i class="fas fa-code text-lg mr-2"></i>
                    <span>链表操作</span>
                </div>
                <div class="flex items-center bg-white/10 backdrop-blur-sm px-4 py-2 rounded-lg">
                    <i class="fas fa-project-diagram text-lg mr-2"></i>
                    <span>归并思想</span>
                </div>
                <div class="flex items-center bg-white/10 backdrop-blur-sm px-4 py-2 rounded-lg">
                    <i class="fas fa-clock text-lg mr-2"></i>
                    <span>时间复杂度 O(n+m)</span>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-5xl mx-auto px-4 sm:px-6 lg:px-8 py-12">
        <!-- Problem Description -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-12 h-12 rounded-full bg-indigo-100 flex items-center justify-center mr-4">
                    <i class="fas fa-question text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold text-gray-800">题目描述</h2>
            </div>
            <div class="prose prose-lg max-w-none text-gray-700">
                <p>将两个升序链表合并为一个新的<strong class="highlight">升序链表</strong>并返回。新链表由给定的两个链表的所有节点组成。</p>
                <p class="bg-indigo-50 border-l-4 border-indigo-500 px-4 py-2">例如，输入链表 <code class="bg-indigo-100 px-1.5 py-0.5 rounded">1→2→4</code> 和 <code class="bg-indigo-100 px-1.5 py-0.5 rounded">1→3→4</code>，输出合并后的链表 <code class="bg-indigo-100 px-1.5 py-0.5 rounded">1→1→2→3→4→4</code>。</p>
            </div>
        </section>

        <!-- Algorithm Explanation -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-12 h-12 rounded-full bg-indigo-100 flex items-center justify-center mr-4">
                    <i class="fas fa-lightbulb text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold text-gray-800">解题思路</h2>
            </div>
            
            <div class="grid md:grid-cols-2 gap-8">
                <!-- Iterative Method -->
                <div class="card bg-white p-6 rounded-xl shadow-md">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 rounded-full bg-blue-100 flex items-center justify-center mr-3">
                            <i class="fas fa-code-branch text-blue-600"></i>
                        </div>
                        <h3 class="text-xl font-semibold text-gray-800">迭代法</h3>
                    </div>
                    <div class="prose text-gray-700 mb-4">
                        <p>使用<strong class="highlight">哑节点(dummy node)</strong>简化操作，比较两个链表的节点值，依次合并。</p>
                        <ul class="list-disc pl-5 space-y-1">
                            <li>时间复杂度: O(n + m)</li>
                            <li>空间复杂度: O(1)</li>
                        </ul>
                    </div>
                    <div class="mermaid">
                        graph TD
                            A[初始化哑节点和指针] --> B{两个链表都有节点?}
                            B -- 是 --> C[比较当前节点值]
                            C -->|L1 ≤ L2| D[连接L1节点]
                            C -->|L1 > L2| E[连接L2节点]
                            D --> F[移动L1指针]
                            E --> G[移动L2指针]
                            F --> H[移动结果指针]
                            G --> H
                            H --> B
                            B -- 否 --> I[连接剩余节点]
                            I --> J[返回合并后链表]
                    </div>
                </div>

                <!-- Recursive Method -->
                <div class="card bg-white p-6 rounded-xl shadow-md">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 rounded-full bg-purple-100 flex items-center justify-center mr-3">
                            <i class="fas fa-sitemap text-purple-600"></i>
                        </div>
                        <h3 class="text-xl font-semibold text-gray-800">递归法</h3>
                    </div>
                    <div class="prose text-gray-700 mb-4">
                        <p>递归选择较小值的节点作为新链表的头，递归处理剩余部分。</p>
                        <ul class="list-disc pl-5 space-y-1">
                            <li>时间复杂度: O(n + m)</li>
                            <li>空间复杂度: O(n + m)（递归栈）</li>
                        </ul>
                    </div>
                    <div class="mermaid">
                        graph TD
                            A{链表是否为空?} -- L1为空 --> B[返回L2]
                            A -- L2为空 --> C[返回L1]
                            A -- 都不空 --> D{比较L1和L2的值}
                            D -- L1 ≤ L2 --> E[L1.next = 递归合并L1.next和L2]
                            D -- L1 > L2 --> F[L2.next = 递归合并L1和L2.next]
                            E --> G[返回L1]
                            F --> H[返回L2]
                    </div>
                </div>
            </div>
        </section>

        <!-- Example Code -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-12 h-12 rounded-full bg-indigo-100 flex items-center justify-center mr-4">
                    <i class="fas fa-laptop-code text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold text-gray-800">示例代码（迭代法）</h2>
            </div>
            
            <div class="code-block rounded-lg overflow-hidden">
                <div class="code-header flex items-center">
                    <div class="flex space-x-2 mr-4">
                        <div class="w-3 h-3 rounded-full bg-red-500"></div>
                        <div class="w-3 h-3 rounded-full bg-yellow-500"></div>
                        <div class="w-3 h-3 rounded-full bg-green-500"></div>
                    </div>
                    <span>MergeTwoLists.java</span>
                </div>
                <div class="code-body">
                    <pre><code class="text-sm md:text-base">/**
 * 链表节点定义
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 创建哑节点作为合并链表的起点，简化边界情况处理
    ListNode dummy = new ListNode(0);
    // 当前指针，用于构建新链表
    ListNode curr = dummy;
    
    // 当两个链表都还有节点时，比较并合并
    while (l1 != null && l2 != null) {
        // 比较两个链表当前节点的值
        if (l1.val <= l2.val) {
            // 如果l1的值较小，将l1添加到结果链表
            curr.next = l1;
            // l1指针前移
            l1 = l1.next;
        } else {
            // 如果l2的值较小，将l2添加到结果链表
            curr.next = l2;
            // l2指针前移
            l2 = l2.next;
        }
        // 结果链表指针前移
        curr = curr.next;
    }
    
    // 将剩余的链表直接接到结果链表末尾
    // 如果l1还有剩余节点，接上l1；否则接上l2（可能也为空）
    curr.next = l1 != null ? l1 : l2;
    
    // 返回合并后的链表（跳过哑节点）
    return dummy.next;
}</code></pre>
                </div>
            </div>
        </section>

        <!-- Visualization Section -->
        <section>
            <div class="flex items-center mb-6">
                <div class="w-12 h-12 rounded-full bg-indigo-100 flex items-center justify-center mr-4">
                    <i class="fas fa-project-diagram text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold text-gray-800">算法过程可视化</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md p-6">
                <div class="mermaid">
                    %%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#e0e7ff', 'primaryBorderColor': '#4f46e5', 'lineColor': '#4f46e5'}}}%%
                    graph LR
                        subgraph 初始状态
                            A1((1)) --> A2((2)) --> A4((4))
                            B1((1)) --> B3((3)) --> B4((4))
                        end
                        
                        subgraph 第一步
                            C1((1)) --> C2((2)) --> C4((4))
                            D1((1)) --> D3((3)) --> D4((4))
                            E1((1)) --> E1n((1))
                        end
                        
                        subgraph 第二步
                            F2((2)) --> F4((4))
                            G1((1)) --> G3((3)) --> G4((4))
                            H1((1)) --> H1n((1)) --> H2((2))
                        end
                        
                        subgraph 第三步
                            I2((2)) --> I4((4))
                            J3((3)) --> J4((4))
                            K1((1)) --> K1n((1)) --> K2((2)) --> K3((3))
                        end
                        
                        subgraph 最终结果
                            L1((1)) --> L1n((1)) --> L2((2)) --> L3((3)) --> L4((4)) --> L4n((4))
                        end
                </div>
                
                <div class="prose mt-6">
                    <p class="text-gray-700">可视化说明：</p>
                    <ol class="list-decimal pl-5 space-y-2">
                        <li>初始状态有两个有序链表：1→2→4 和 1→3→4</li>
                        <li>每次比较两个链表的当前节点，选择较小的节点连接到结果链表</li>
                        <li>当一个链表遍历完成后，直接将另一个链表剩余部分连接到结果链表末尾</li>
                        <li>最终得到合并后的有序链表：1→1→2→3→4→4</li>
                    </ol>
                </div>
            </div>
        </section>
    </main>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>